package com.zklh.leetcode.greedy.middle.problem55;
/**
 * @descrpiton 跳跃游戏1算法实现
 * @author 坐看落花
 * @version 1.0
 * @date 2020/6/4
 */
public class Solution {
    public boolean canJump(int[] nums) {

        // 当前落脚点能到达的最远索引
        int stanceExtend = nums[0];
        // 下个落脚点能到达的最远距离索引, 改值会不断刷新
        int nextStanceExtend = 0;
        // 上个落脚点能到达的最远距离
        int lastStanceExtend = 0;

        while (stanceExtend < nums.length-1 && stanceExtend > lastStanceExtend) {
            for (int i = lastStanceExtend+1; i <= stanceExtend; i++) {
                // 如果 stance 和 stanceExtend 中间有节点能跳到比上个记录的最远节点更远, 则刷新
                if (nums[i]+i > nextStanceExtend) {
                    nextStanceExtend = nums[i]+i;
                }
            }
            lastStanceExtend = stanceExtend;
            stanceExtend = nextStanceExtend;
        }

        return stanceExtend >= nums.length-1;
    }

    public static void main(String[] args){
        Solution solution = new Solution();
        System.out.println(solution.canJump(new int[]{2, 3, 1, 1, 4}));
        System.out.println(solution.canJump(new int[]{3,2,1,0,4}));
        System.out.println(solution.canJump(new int[]{2,5,0,0}));
    }
}

